package cn.bellychang.leetcode.question035;

/**
 * @author ChangLiang
 * @date 2021/3/8
 */
public class Solution {

    public int searchInsert(int[] nums, int target) {

        if(nums[0] >= target){
            return 0;
        }
        if(nums[nums.length - 1] < target){
            return nums.length;
        }
        if(nums[nums.length - 1] == target){
            return nums.length - 1;
        }

        int begin = 0;
        int end = nums.length - 1;
        while(begin<end){
            int mid = ((end - begin) >> 2) + 1 + begin;
            if(nums[mid]>target){
                end = mid - 1;
            }else{
                begin = mid;
            }
        }
        if(nums[end]==target){
            return end;
        }else{
            return end+1;
        }
    }
}
